1. Concepte de baza
1.1 Necesitatea acestei discipline
Structurile de date sunt strict legate de programarea intyr-un limbaj de programare.
Daca se considera structurile de date S1, S2, S3, ...., Sn, , pentru o problema PROB se scriu n variante de program, fiecare avand cate o structura de date dominanta.
Se vor scrie, respectiv programele PROG1, PROG1, PROG2, ......, PROGn.
Necesitatea studierii disciplinei de structuri de date se impune prin:
- alegerea celei mai adecvate structuri de date
- efortul de programare sa fie cat mai mic
- programul sa conduca la durate ale tranzactiilor cat mai reduse
- programul sa fie cat mai usor de intretinut
- depanarea sa necesite eforturi mici
- cunoasterea proprietatilor fiecarei structuri de date
- construirea si utilizarea de biblioteci de proceduri pentru fiecare structura.
Programatorii in loc sa construiasca n variante de program VAR1, VAR2, VAR3, ....., VARn, de program si dupa aceea sa masoare performanta.
Alegerea se efectueaza dupa ce au fost analizate cele n variante.
Este scump sa se procedeze astfel daca raman n-1 variante pentru care s-au cheltuit sume importante fara a fi utilizate numai pentru ca nu sunt performante.
Daca se cunosc toate tipurile de structuri de date, proprietatile si mai ales efectele utilizarii lor asupra eficientei programului, evident:
- se construiesc un numar foarte restrans de variante
- se alege varianta cea mai performanta dintr-un numar foarte restrans de variante
- se fac cheltuieli mult mai mici.
Cunoasterea structurilor de date permite programatorilor sa priveasca procesul de dezvoltare software ca proces de alocare si nivelare de resurse.
Instructiunile sunt resurse.
Limbajele de programare sunt resurse.
Fisierele si organizarile lor sunt resurse.
Bibliotecile de subprograme, bibliotecile de clase, sunt resurse.
Este important ca programatorul sa aleaga acele resurse care conduc spre progrtame eficiente la:
- nivelul firmei care dezvolta software
- utilizator prin maximizarea gradului de satisfactie a acestuia.
1.2 Obiectivul
Despre structuri de date se invata la multe discipline, precum:
- limbaje de programare
- birotica
- sisteme de calcul
- baze de date
- programe aplicative.
Sistematizarea cunostintelor insa este efectuata numai la disciplina STRUCTURI DE DATE care are ca obiectiv prezentarea tuturor structurilor de date cu proprietatile, avantajele si dezavantajele utilizarii lor, in vederea utilizarii lor eficiente.
Pentru aceasta trebuie sa se;
- enumere structurile
- clasifice structurile de date
- prezinte fiecare structura
- construiasca proceduri pentru implementarea operatiilor
- dezvolte metrici ale structurilor de date
- arate cum se agrega structurile de date
- clarifice ce inseamna utilizare eficienta
- arate care sunt limitele procesului de optimizare.
1.3 Criterii de clasificare
Dupa criteriului alocarii memoriei exista structuri de date:
- statice
- dinamice.
Dupa numarul pointerilor de referire elemente exista structuri cu:
- zero pointeri
- un pointer
- doi pointeri
- mai multi pointeri.
Dupa disciplina de parcurgere:
- LIFO
- FIFO
- RSD
- SDR
- DSR.
1.4 Modele de prezentare a srtucturilor de date
- modelul grafic presupune: definire zone de memorie si legaturi cu arce orientate
- modelul analitic presupune utilizarea funtiilor tip(), prec(), succ(), cont(), adr(), in(), out()
- modelul graf utilizeaza noduri si arce
- modelul textual utilizeaza cuvinte din limbajul natural
- modelul sintactic utilizeaza conventiile limbajelor de programanre.
1.5 Operatii cu structuri de date
Indiferent care sunt structurile de date, se definesc urmatoarele operatii:
- creare element
- adaugare element
- traversare structura
- concatenare doua sau mai multe structuri de acelasi tip
- cautare element dupa cheie sau pozitie
- interschimb elemente adiacente
- interschimb elemente oarecare
- manipulare de legauri
- manipulare de informatii utile
- stergere element
- stergere structura
- numarare elemente
- modificare campuri
- inserare element dupa pozitie
- inserare element cu pastrarea unei proprietati
- copierea de informatii utile
- echilibrare
- sortare fara mentinerea vechilor legaturi
- sortare cu mentinerea vechilor legaturi
- compunere de structuri de acelasi tip.
Pentru fiecare structura se construieste o biblioteca de proceduri care implementeaza aceste operatii, in forma nerecursiva sau in forma recursiva.
